package two.chapter_4.c4_2;

import edu.princeton.cs.algs4.StdOut;
import two.chapter_4.c4_1.SymbolGraph;

/**
 * 拓扑排序
 */
public class Topological {

    private Iterable<Integer> order;//顶点的拓扑排序
    public Topological(Digragh g){
        DirectedCycle cycleFinder=new DirectedCycle(g);
        if (!cycleFinder.hasCycle()){
            DepthFirstOrder dfs=new DepthFirstOrder(g);
            order=dfs.postReverse();
        }
    }

    /**
     * g是有向无环图吗
     * @return
     */
    public boolean isDAG(){
        return order!=null;
    }

    /**
     * 拓扑排序的所有顶点
     * @return
     */
    public Iterable<Integer> order(){
            return order;
    }

    public static void main(String [] args){
        String graphPath="/Users/wind/downloads/高焕堂EIT/Algorithms-master/data/jobs.txt";
        String delim="/";
        SymbolDigraph sg=new SymbolDigraph(graphPath,delim);
        Topological top=new Topological(sg.g());
        for (int v:top.order()){
            StdOut.println(sg.name(v));
        }
    }
}
